package com.study.lihan.letcode.util;

import com.study.lihan.letcode.ListNode;

import javax.xml.transform.Source;
import java.util.Arrays;

public class Util {
    public static void main(String[] args) {
        int[] arr = generateArr(10);
        int[] tempArr = Arrays.copyOf(arr, arr.length);
        int[] resultArr = stackSort(tempArr);
        Arrays.sort(arr);
        System.out.println(isIntArrEqul(arr, resultArr));
    }
    private Util() {
    }

    public static void printArr(int[] arr){
        Arrays.stream(arr).forEach(o-> System.out.print(o+","));
    }

    public static ListNode generateListNode(int[] nums){
        ListNode head = new ListNode(nums[0],null);
        ListNode tail = head;
        for(int i =1; i<nums.length; i++){
            ListNode next = new ListNode(nums[i],null);
            tail.next = next;
            tail= next;

        }
        return  head;
    }

    public static int[] generateArr (int len){
        int[] arr = new int[len];
        for (int i = 0; i < len ; i++) {
            arr[i] = (int) (Math.random() * 100);
        }
        return arr;
    }

    public static boolean isIntArrEqul(int[] arr1, int[] arr2){
        boolean flag = true;
        for (int i = 0; i < arr1.length ; i++) {
            if (arr1[i] != arr2[i]){
                flag = false;
                break;
            }
        }
        return flag;
    }

    //堆排序，不稳定
    public static int[] stackSort(int[] arr){
        int[] resultArr =  new int[arr.length];
        int len = arr.length - 1;
        int tail = (len -1)/2;
        for (int i = tail; i >=0 ; i--) {
            shift(arr, i, len);
        }
        int curIndex = len;
        while (curIndex != 0){
            resultArr[len - curIndex] = arr[0];
            arr[0] = arr[curIndex];
            curIndex --;
            shift(arr, 0, curIndex);
        }
        resultArr[len - curIndex] = arr[0];
        return resultArr;

    }
    public static void shift (int[] arr, int low, int high){
        int curIndex = low;
        int minValIndex = -1;
        while (curIndex <= high){
            minValIndex = 2 * curIndex +1;
            if (minValIndex > high){
                return;
            }
            if (minValIndex +1 <= high && arr[minValIndex + 1] < arr[minValIndex]){
                minValIndex++;
            }
            if ( arr[minValIndex] > arr[curIndex]){
                return;
            }
            int temp = arr[minValIndex];
            arr[minValIndex] = arr[curIndex];
            arr[curIndex]=  temp;
            curIndex = minValIndex;
        }
    }
}
